package leetcode.map;

import java.util.*;

public class Lc743_2 {



    public static final int INF = Integer.MAX_VALUE / 2;

    public int networkDelayTime(int[][] times, int n, int k) {

        List<int[]>[] graph = new ArrayList[n + 1]; //存储每个节点的后继节点和对于的权值

        for (int i = 0; i <= n ; i++) {
            graph[i] = new ArrayList<int[]>();
        }
        for (int[] time : times) {
            graph[time[0]].add(new int[]{time[1], time[2]});
        }
        // 存储最近加入已确定最短路节点的后继节点，及对于的权值, int[0] 存在权值，int[1]存储节点编号，以权值从小到大排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        int[] dist = new int[n + 1]; //存储每个节点的最短路径
        Arrays.fill(dist, INF);
        dist[k] = 0;
        dist[0] = 0; //节点编号从0 开始
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[1];
            //更新u所有的后继节点dist
            for (int[] neighbor : graph[u]) {
                int v = neighbor[0];
                int cost = neighbor[1];
                if (dist[v] > dist[u] + cost) {
                    dist[v] = dist[u] + cost;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;
    }


    public static void main(String[] args) {
        Lc743_2 lc743_2 = new Lc743_2();
        int[][] t = {{2,1,1},{2,3,1},{3,4,1}};
        System.out.println(lc743_2.networkDelayTime(t, 4, 2));
    }










}
